perm filename PUZZ.DDG[ESS,JMC]1 blob
sn#182424 filedate 1975-10-19 generic text, type T, neo UTF8
00100 Here is the solution to your puzzle of last night: Let p(n) be the
00200 position mod n of the person who should be in the n th place and
00300 let r(n) be the amount the table must be rotated to bring him to
00400 his correct place - all assuming N people numbered 0,1,...,N-1.
00500 Unless the N r(n)'s are precisely the N numbers 0,1,...,N-1,
00600 rotating by the missing number will bring everyone to the wrong place.
00700 If they are, then adding up the N congruences p(n) + r(n) = n mod N,
00800 each expressing that rotating the table by r(n) will bring the
00900 person who should be at position n from position p(n) to that position,
01000 gives the congruence (N↑2-N)/2 + (N↑2-N)/2 ≡ (N↑2-N)/2 mod N.
01100 since the first summands, the second summands and the right hand sides
01200 each form the set {0,1,...,N-1}. Setting N = 2K gives a left side
01300 congruent to zero and a right side congruent to K. This shows that
01400 the r(n)'s cannot be all different, and so there must be a rotation
01500 ←utting everyone in the wrong place.
01600
01700 If N is odd, then setting p(n) = -n, i.e. reversing the
01800 order of the guests produces a configuration in which any rotation
01900 puts some guest in the right position, because then r(n) = 2n, and
02000 since 2 and N are relatively prime, the 2n are again a complete
02100 set of residues. The only remaining question is what other suitable
02200 configurations exist in the odd case.